package com.LeeCode;

import java.util.TreeSet;

/**
 * 矩形区域不超过 K 的最大数值和
 */

public class Code363 {

    public static void main(String[] args) {
        int[][] matrix = {
                {1, 0, 1},
                {0, -2, 3}
        };
        int k = 2;
        System.out.println(new Code363().maxSumSubmatrix(matrix, k));
    }

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int m = matrix.length, n = matrix[0].length;
        int ans = Integer.MIN_VALUE;

        for (int i = 0; i < m; i++) { // 枚举上界
            int[] colSum = new int[n];
            for (int i2 = i; i2 < m; i2++) { // 枚举下界
                for (int j = 0; j < n; j++) {
                    colSum[j] += matrix[i2][j]; // 安列求和
                }
                // 求解一维问题
                int subAns = solveSubarray(colSum, k);
                ans = Math.max(ans, subAns);
            }
        }
        return ans;
    }

    private int solveSubarray(int[] nums, int k) {
        TreeSet<Integer> cnt = new TreeSet<>();
        cnt.add(0);
        int preSum = 0, ans = Integer.MIN_VALUE;
        for (int num : nums) {
            preSum += num;
            // 找到符合条件的数字
            Integer upper = cnt.ceiling(preSum - k);
            if (upper != null) {
                ans = Math.max(ans, preSum - upper);
            }
            cnt.add(preSum);
        }
        return ans;
    }
}
